Search for: All records

In the game of Matching Pennies, Alice and Bob each hold a penny, and at every tick of the clock they simultaneously display the head or the tail sides of their coins. If they both display the same side, then Alice wins Bob's penny; if they display different sides, then Bob wins Alice's penny. To avoid giving the opponent a chance to win, both players seem to have nothing else to do but to randomly play heads and tails with equal frequencies. However, while not losing in this game is easy, not missing an opportunity to win is not. Randomizing your own moves can be made easy. Recognizing when the opponent's moves are not random can be arbitrarily hard. The notion of randomness is central in game theory, but it is usually taken for granted. The notion of outsmarting is not central in game theory, but it is central in the practice of gaming. We pursue the idea that these two notions can be usefully viewed as two sides of the same coin. The resulting analysis suggests that the methods for strategizing in gaming and security, and for randomizing in computation, can be leveraged against each other. 2010 Mathematics Subject Classification. 03D32,91A26,91A26, 68Q32. 

Heterogeneity in computing systems is clearly increasing, especially as “accelerators” burrow deeper and deeper into different parts of an architecture. What is new, however, is a rapid change in not only the number of such heterogeneous processors, but in their connectivity to other structures, such as cores with different ISAs or smart memory interfaces. Technologies such as chiplets are accelerating this trend. This paper is focused on the problem of how to architect efficient systems that combine multiple heterogeneous concurrent threads, especially when the underlying heterogeneous cores are separated by networks or have no shared-memory access paths. The goal is to eliminate today’s need to invoke significant software stacks to cross any of these boundaries. A suggestion is made of using migrating threads as the glue. Two experiments are described: using a heterogeneous platform where all threads share the same memory to solve a rich ML problem, and a fast PageRank approximation that mirrors the kind of computation for which thread migration may be useful. Architectural “lessons learned” are developed that should help guide future development of such systems.} 

Chemical reaction networks (CRNs) are an important tool for molecular programming. This field is rapidly expanding our ability to deploy computer programs into biological systems for various applications. However, CRNs are also difficult to work with due to their massively parallel nature, leading to the need for higher-level languages that allow for more straightforward computation with CRNs. Recently, research has been conducted into various higher-level languages for deterministic CRNs but modeling CRN parallelism, managing error accumulation, and finding natural CRN representations are ongoing challenges. We introduce Reactamole, a higher-level language for deterministic CRNs that utilizes the functional reactive programming (FRP) paradigm to represent CRNs as a reactive dataflow network. Reactamole equates a CRN with a functional reactive program, implementing the key primitives of the FRP paradigm directly as CRNs. The functional nature of Reactamole makes reasoning about molecular programs easier, and its strong static typing allows us to ensure that a CRN is well-formed by virtue of being well-typed. In this paper, we describe the design of Reactamole and how we use CRNs to represent the common datatypes and operations found in FRP. We demonstrate the potential of this functional reactive approach to molecular programming by giving an extended example where a CRN is constructed using FRP to modulate and demodulate an amplitude-modulated signal. We also show how Reactamole can be used to specify abstract CRNs whose structure depends on the reactions and species of its input, allowing users to specify more general CRN behaviors. 

Rigorous, mathematical reasoning, i.e., proof, is the foundation of any undergraduate computer science education. However, students find mathematical proof exceedingly challenging, but also at the same time do not see its relevance to programming. We address these concerns with Snowflake, an educational proof assistant designed to help undergraduates overcome these difficulties when authoring mathematical proof. Snowflake does this by operating in a context where mathematical proof is introduced alongside programming in either a CS1 or CS2 context. The lens that we use to unite the two concepts is program correctness, a topic that immediately makes relevant the concept of formal reasoning as students are perpetually faced with the issue of whether their code is correct. Snowflake is a proof assistant designed for the needs of undergraduates in courses that closely time programming and proof. It is a web-based application that helps students author proofs not only in the context of program correctness in-the-small, but also other topics found in discrete mathematics courses. We report on the design of Snowflake, the kinds of reasoning it enables, and our plans to deploy Snowflake in the classroom. 

Notional Machines (NMs) are a pedagogical device used by teachers in order to help students understand certain concepts. While NMs have been cataloged, the effectiveness of NMs has been rarely evaluated. We build upon this research by exploring what makes certain NMs more effective in various computer science and mathematics courses. We interview professors and students to assess NMs used in the classroom. Notably we found that most students are able to employ the NMs introduced by their professors, and that introductory students prefer template-like NMs, whereas upper level students rely on more conceptual NMs.